<?php
/**
 * 对一个数组内的元素实现翻转
 *
 * @param array $array 给定的数组
 * @return 返回翻转之后的新数组
 */
function reverse($array) 
{
    $n = count($array);
    for ($i = 0; $i < $n / 2; $i++) {
        // 交换
        swap($array[$i], $array[$n - $i - 1]);
    }
    return $array;
}

/**
 * 对一个数组内的元素实现翻转
 *
 * @param array $array 给定的数组, 按引用传递
 */
function reverse2(&$array) 
{
    $n = count($array);
    for ($i = 0; $i < $n / 2; $i++) {
        // 交换
        swap($array[$i], $array[$n - $i - 1]);
    }
}

/**
 * 交换两个元素
 *
 * @param $a
 * @param $b
 */
function swap(&$a, &$b) 
{
    $tmp = $a;
    $a = $b;
    $b = $tmp;
}

/**
 * 插入排序
 *
 * @param array $array
 * @return 返回排序之后的新数组
 */
function insertSort($array) 
{
    $sorted = [];
    // 实现插入排序算法
    foreach ($array as $element) {
        // 寻找第一个比当前元素$element大的元素的位置
        $isMax = true;
        $position = count($sorted);
        for ($i = 0; $i < count($sorted); $i++) {
            if ($element < $sorted[$i]) {
                $isMax = false;
                $position = $i;
                break;
            }
        }

        // 移动$position及其之后的元素, 并插入新元素
        insert($sorted, $position, $element);
    }

    return $sorted;
}

/**
 * 把新元素插入给定数组的指定的位置
 *
 * @param array $array 按引用传递的数组
 * @param $element 要插入的新元素
 * @param integer $position 指定要插入新元素的位置,默认值为-1表示不指定位置，插入数组末尾
 * @return true表示插入成功, false表示插入失败
 */
function insert(&$array,$element,$position = -1) 
{
    if ($position == -1) {
        $array[] = $element;
        return true;
    }
    if (($position < 0) || ($position > count($array))) {
        return false;
    }

    // 从后向前移动$position及其之后位置的元素
    $n = count($array);
    for ($i = $n - 1; $i >= $position; $i--) {
        $array[$i + 1] = $array[$i];
    }
    // 在$position位置放入新元素
    $array[$position] = $element;
    return true;
}
